Sebaik sahaja Milton habisi pengajiannya dan kembali ke Uganda tahun 1956, beliau menyertai parti Kongres Kebangsaan Uganda. Beliau dilantik memasuki Majlis Perundangan Jajahan (Legislative Council) tahun 1957.[3]

Pada tahun 1959, parti Kongres Kebangsaan terbahagi kepada dua puak; satu puak pimpinan Obote bergabung dengan Kesatuan Rakyat Uganda (Uganda People's Union) membentuk Kongres Rakyat Uganda. Parti Kongres Rakyat Uganda membentuk suatu perikatan dengan Kabaka Yekka, sebuah parti politik royalis Buganda. Gabungan tersebut memenangi kebanyakan kerusi dalam Parlimen dan Obote dilantik Walter Coutts, Gabenor Jeneral Uganda sebagai Perdana Menteri pada 25 April 1962.

Pada tahun berikutnya, jawatan Gabenor Jeneral digantikan dengan suatu jawatan Presiden lantikan parlimen; Raja (atau Kabaka) Mutesa II dilantik sebagai Presiden manakala Obote menjadi Perdana Menteri eksekutif dalam kerajaan tersebut.[2]